Modem data processing systems typically incorporate address translation schemes. Address translation is a process of mapping the memory address manipulated by the system's data processor into an address presented to the system's memory system. Typically, the address manipulated by the data processing system's data processor is referred to as an "effective" or a "logical" address. Conversely, the address presented the data processing system's communications bus is referred to as a "real" or a "physical" address.
Address translation schemes improve the performance of a data processing system for at least three reasons. First, address translation schemes may be used to define certain useful characteristics about particular sections of main memory. For instance, these characteristics may prevent the system's data processor from writing to input/output devices during certain modes of operation or may restrict other regions of memory from being cached in the data processor's memory cache. Also, multiple software applications can be resident in the data processor's memory at the same time without fear of one program corrupting another program. Second, address translation schemes allow the data processor to execute programs that are larger than the system's random access memory ("RAM"). The majority of these very large programs are stored in permanent memory devices (hard disk drives, magnetic tape drives, etc.). Smaller portions of these very large programs are recalled into the system's RAM as needed. This feature is known as "virtual memory." Third, more than one data processor in a multi-processor data processing system ("MP") can easily access the same data stored in memory. Each data processor in an MP system can use a different address to access the same location in memory. This feature simplifies software programming of such a system. This feature may also be used by multiple programs executing in a single data processor data processing system.
There are three basic types of address translation schemes: paging, segmentation, and combined paging/segmentation. These three schemes each have advantages and disadvantages with respect to each other known in the art.
In a paging addressing scheme, the main memory is divided into a number of fixed-size blocks ("pages"). A certain number of address bits (most significant bits) of each effective address generated by the data processor identify a selected page in memory. The remaining number of address bits of each effective address (least significant bits) identify a byte within the selected page. Pages are often relatively small. Therefore, page translation data is voluminous and is stored in a table.
In a segmentation addressing scheme, the main memory is divided into a number of variable-size blocks ("segments"). The most and least significant bits of each effective address generated by the data processor identify a segment and a byte within the selected segment, respectively. Originally, a data processing system's operating system program code, its application program code, its application program data, and its pointer stack were each mapped to a different one of four segments in main memory. Consequently, the size of a segment has developed to be several orders of magnitude larger than the size of a page. Segment translation data is smaller and therefore may be stored in either a register file or in a table.
In a paging/segmentation scheme, the main memory is also divided into pages. However, each effective address is mapped to an intermediate or "virtual" address by a segmentation scheme before being mapped to a particular page in main memory. Again, the least significant bits of the effective address are used to identify a byte within the selected page. In some paging/segmentation schemes, both the page and the segments are fixed-size blocks. The PowerPC Architecture uses such an all fixed-size paging/segmentation addressing scheme.
A segmentation translation scheme may be implemented as either an associative table or a binary-indexed register file. Typically, a particular implementation depends upon how the data processing system adds translation mappings to its segment structure after it is unable to translate a particular effective address. In general, there are two broad methods to add translation mappings to a segment structure: a hardware tablewalk and a software tablewalk. In a hardware tablewalk, data processor 10 automatically searches a memory table for a necessary address translation. This function is invisible to the data processing system's operating system. Tables are appropriate in this case. In a software tablewalk, data processor 10 branches to a program subroutine that generates the necessary translation. This function is part of the data processing system's operating system. In this case, binary-indexed register files are appropriate.